/* 498. 对角线遍历 */
/**
 * @param {number[][]} mat
 * @return {number[]}
 */

/* 
    直接模拟
    设矩阵的行数为m 列数为n 
    一共有 m + n - 1 条对角线
    设对角线从上到小的编号为i ∈ [0,m + n -2]
    当第i条对角线从下往上遍历时，每次行索引减1，列索引加1直到矩阵的边缘为止
    当 i < m 此时的起点 (i,0)
    当 i >= m 时，则此时对角线的起点(m-1,i-m+1)

    当第i条对角线从上往下遍历时，每次列索引-1，行索引+1
    当 i< n 此时起点(0,i)
    当 i>=n此时起点(i-n+1,n-1)

*/
var findDiagonalOrder = function (mat) {
	const m = mat.length
	const n = mat[0].length

	const res = new Array(m * n).fill(0)
	let pos = 0
	for (let i = 0; i < m + n - 1; i++) {
		if (i % 2 === 1) {
			let x = i < n ? 0 : i - n + 1
			let y = i < n ? i : n - 1
			while (x < m && y >= 0) {
				res[pos++] = mat[x++][y--]
			}
		} else {
			/* 
                y 属于 [0,n-1]
                i = m + n - 1
                i - m + 1 = m + n - 1 - m + 1 = n
            */
			let x = i < m ? i : m - 1
			let y = i < m ? 0 : i - m + 1
			while (x >= 0 && y < n) {
				res[pos++] = mat[x--][y++]
			}
		}
	}
	return res
}

const res = findDiagonalOrder([
	[1, 2, 3],
	[4, 5, 6],
	[7, 8, 9],
])
